import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    char[] c;
    int[][] visited;
    int row, col;
    int[][] direc = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    boolean flag = false;

    public void dfs(char[][] matrix, int index, int i, int j) {
        System.out.printf("%d, %d, %d\n", i, j, index);
        
        visited[i][j] = 1;
        index++;

        if (index == c.length) {
            flag = true;
            return ;
        }

        for (int t = 0; t < 4; t++) {
            int x = i + direc[t][0];
            int y = j + direc[t][1];
            if (x >= 0 && y >= 0 && x < row && y < col) {
                if (visited[x][y] == 0 && matrix[x][y] == c[index]) {
                    dfs(matrix, index, x, y);
                }
            }
        }

        visited[i][j] = 0;
        index--;
        
        return ;
    }
    

    public boolean hasPath (char[][] matrix, String word) {
        // write code here

        row = matrix.length;
        col = matrix[0].length;
         
        if (row == 0 && col == 0)
            return false;

        c = word.toCharArray();
        visited = new int[row][col];
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (visited[i][j] == 0 && matrix[i][j] == c[0]) {
                    dfs(matrix, 0, i, j);
                    if (flag) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}